package com.leetcode.LC_MED;

public class LC70 {
    //举个例子就理解了，比如如果需要走到第3阶，
    // 由于一次最多只能走两阶，只有两种可能，要么从第1阶走2阶过来，
    // 要么从第2阶走1阶过来，所以第3阶所有的步数就是第1、2这两阶的步数的和，
    // 这样往下累加就行了，直到累加到第n阶，n-2,n-1这两阶步数的和就是答案。
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }
}
